It is often desirable to automatically rewrite a string of text (e.g., a phrase, sentence(s), a paragraph, or other segment of text) to achieve one or more desired objectives. Generally, rewriting a string of text involves converting the string into a rephrased output. For example, a string of text that is a sentence may be rewritten to achieve the objective of sentence compression; and the rephrased output may be a compressed version of the sentence. Various computer-implemented techniques have been utilized to automatically rewrite a textual string. As one example, some techniques relate to the automatic compression of natural language sentences to determine a compressed version of a sentence that is grammatical and/or that preserves certain information from the uncompressed sentence.